package q699_fallingSquares;

import java.util.ArrayList;
import java.util.List;

public class Solution_1 {
    /*
    暴力解法 每次加入一个新的方块时
    考虑它是否落到了之前某一个方块的范围上
    如果落在了范围内 则根据之前每个落在范围内的方块height所记录的最高值 进一步更新height

    但是方法最后需要考虑 例如
    [[1,2],[2,3],[6,1]]
    如果至通过暴力搜索只会得到 2 5 1 的答案 实际上则是 2 5 5
    所以我们还要循环一次 考虑每次(heights.get(i - 1), heights.get(i))的max
    也就是上一次的结果如果大于本次结果 则需要更新答案
     */
    public List<Integer> fallingSquares(int[][] positions) {
        List<Integer> heights = new ArrayList<>();
        for (int i = 0; i < positions.length; i++) {
            int l1 = positions[i][0], r1 = positions[i][0] + positions[i][1];
            int height = positions[i][1];

            for (int j = 0; j < i; j++) {
                int l2 = positions[j][0], r2 = positions[j][0] + positions[j][1];
                if (r2 > l1 && l2 < r1) {
                    height = Math.max(height, heights.get(j) + positions[j][1]);
                }
            }

            heights.add(height);
        }

        for (int i = 1; i < heights.size(); i++) {
            heights.set(i, Math.max(heights.get(i - 1), heights.get(i)));
        }

        return heights;
    }
}
